package main

// 就是在 直接插入排序顺序查找位置的基础上 使用二分优化位置查找
func BInsertSort(nums []int) {
	for i := 1; i < len(nums); i++ {
		temp := nums[i]
		j := i
		// 使用二分进行查找（经典问题）: 查找到比当前元素小的 第一个元素下标（没有返回默认下标 -1）
		l, r, mid := 0, j-1, 0
		// 二分查找有两种， 第一种是 l < r, 一种 l <= r 这里元素可能只有一个，要使用第二种找到位置
		for l <= r {
			// 计算mid
			mid = l + (r-l)/2
			if nums[mid] >= temp {
				// 判断前面的元素是否小于目标值
				// 或者当前元素是否已经是第一个元素
				if mid == 0 || nums[mid-1] < temp {
					// 使用mid 标记需要的位置
					mid = mid - 1
					break
				} else {
					r = mid - 1
				}
			} else {
				// 避免死循环
				l = mid + 1
			}
		}
		// 开始进行移动
		for ; j > mid+1; j-- {
			nums[j] = nums[j-1]
		}
		nums[j] = temp
	}
}
